package com.wang.sort;

import java.util.HashMap;
//前缀树的实现，又叫字典树
public class Demo24_TrieTree {
    //使用自定义的数组实现
    public static class Node1 {
        public int pass;
        public int end;
        public Node1[] nexts;

        public Node1() {
            pass = 0;
            end = 0;
            //以26个小写字母举例，即有26条通路
            //index    Char
            //0        a
            //1        b
            //...      ...
            //25       z
            //nexts[i] == null  i方向的路不存在
            //nexts[i] != null  i方向的路存在
            nexts = new Node1[26];
        }

        public static class Trie1 {
            private Node1 root;

            public Trie1() {
                root = new Node1();
            }

            //插入
            public void insert(String word) {
                if (word == null) {
                    return;
                }
                char[] str = word.toCharArray();
                Node1 node = root;
                node.pass++;
                int path = 0;
                for (int i = 0; i < str.length; i++) {
                    path = str[i] - 'a'; //由字符来决定走哪一条路
                    if (node.nexts[path] == null) {
                        node.nexts[path] = new Node1();
                    }
                    node = node.nexts[path];
                    node.pass++;
                }
                node.end++;
            }

            //所有加入的字符串中，有多少个字符串是以pre字符串作为前缀的
            public int prefixNums(String pre) {
                if (pre == null) {
                    return 0;
                }
                char[] str = pre.toCharArray();
                Node1 node = root;
                int path = 0;
                for (int i = 0; i < str.length; i++) {
                    path = str[i] - 'a';
                    if (node.nexts[path] == null) {
                        return 0;
                    }
                    node = node.nexts[path];
                }
                return node.pass;
            }

            //搜索(查找之前的word加入过几次)
            public int search(String word) {
                if (word == null) {
                    return 0;
                }
                char[] str = word.toCharArray();
                Node1 node = root;
                int path = 0;
                for (int i = 0; i < str.length; i++) {
                    path = str[i] - 'a';
                    if (node.nexts[path] == null) {
                        return 0;
                    }
                    node = node.nexts[path];
                }
                return node.end;
            }

            //删除一个字符串
            public void delete(String word) {
                if (search(word) == 0) {
                    return;
                }
                char[] str = word.toCharArray();
                Node1 node = root;
                node.pass--;
                int path = 0;
                for (int i = 0; i < str.length; i++) {
                    path = str[i] - 'a';
                    //一旦发现node的下一个节点pass值为0，直接把其释放，让jvm回收
                    if (--node.nexts[path].pass == 0) {
                        node.nexts[path] = null;
                        return;
                    }
                    node = node.nexts[path];
                }
                node.end--;
            }
        }
    }
    //前缀树使用hashmap实现
    public static class Node2 {
        public int pass;
        public int end;
        public HashMap<Integer, Node2> nexts;

        public Node2() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }

        public static class Trie2 {
            private Node2 root;

            public Trie2() {
                root = new Node2();
            }
            //
            public void insert(String word) {
                if(word == null) {
                    return;
                }
                char[] str = word.toCharArray();
                Node2 node = root;
                node.pass++;
                int index = 0;
                for (int i = 0; i < str.length; i++) {
                    index = (int) str[i];
                    if (!node.nexts.containsKey(index)) {
                        node.nexts.put(index, new Node2());
                    }
                    node = node.nexts.get(index);
                    node.pass++;
                }
                node.end++;

            }
            //搜索(查找之前的word加入过几次)
            public int search(String word) {
                if (word == null) {
                    return 0;
                }
                char[] str = word.toCharArray();
                Node2 node = root;
                int index = 0;
                for (int i = 0; i < str.length; i++) {
                    index = (int) str[i];
                    if (!node.nexts.containsKey(index)) {
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.end;
            }
            //删除一个字符串
            public void delete(String word) {
                if (search(word) == 0) {
                    return;
                }
                char[] str = word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < str.length; i++) {
                    index = (int) str[i];
                    //一旦发现node的下一个节点pass值为0，直接把其释放，让jvm回收
                    if (--node.nexts.get(index).pass == 0) {
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }

            //所有加入的字符串中，有多少个字符串是以pre字符串作为前缀的
            public int prefixNums(String pre) {
                if (pre == null) {
                    return 0;
                }
                char[] str = pre.toCharArray();
                Node2 node = root;
                int index = 0;
                for (int i = 0; i < str.length; i++) {
                    index = (int) str[i] ;
                    if (!node.nexts.containsKey(index)) {
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.pass;
            }
        }

    }
    //暴力枚举
    public static class Right {
        private HashMap<String , Integer> box;

        public Right() {
            box = new HashMap<>();
        }
        public void insert(String word) {
            if(! box.containsKey(word)) {
                box.put(word,1);
            }
            else {
                box.put(word, box.get(word) + 1);
            }

        }
        public void delete(String word) {
            if(box.containsKey(word)){
                if(box.get(word) == 1) {
                    box.remove(word);
                }
                else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }
        public int search(String word) {
            if(! box.containsKey(word)) {
                return 0;
            }
            else {
                return box.get(word);
            }
        }
        public int prefixNums(String pre) {
            int count = 0;
            for (String cur: box.keySet()
                 ) {
                if(cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }

    }
}